//
// Description: 96. 不同的二叉搜索树
// Created by Loading on 2021/7/15.
//

#include <bits/stdc++.h>

using namespace std;

// 动态规划
int numTrees_DP(int n) {
    // G(n) 表示长度为 n 的序列能构成的不同二叉搜索树的个数
    vector<int> G(n + 1, 0);
    G[0] = 1;
    G[1] = 1;

    /* 从 1 开始一直到 n，轮流作为二叉树根节点，保证二叉树的唯一性 */
    /* 每个根节点对应的二叉树的数量总和，即为结果 */
    /*
     * 所有小于当前根节点的节点，为其左子树；所有大于当前根节点的节点，为其右子树
     * 左子树数量与右子树数量的笛卡尔积，即为当前根节点的二叉树数量
     */

    /* eg. G(3) = G(0) * G(2) + G(1) * G(1) + G(2) * G(0) */
    /*                 ↑             ↑             ↑      */
    /*             根节点为 1     根节点为 2     根节点为 3  */
    for (int i = 2; i <= n; ++i) {
        for (int j = 1; j <= i; ++j) {
            G[i] += G[j - 1] * G[i - j];
        }
    }
    return G[n];
}

// 数学法
int numTrees_math(int n) {
    /* 卡塔兰数 */
    /* C(0) = 1, C(n+1) = 2 * (2 * n + 1)  / (n + 2) * C(n) */
    long long C = 1;
    for (int i = 0; i < n; ++i) {
        C = C * 2 * (2 * i + 1) / (i + 2);
    }
    return (int) C;
}

int main() {
    int n = 3;
    cout << numTrees_DP(n) << endl;

    cout << numTrees_math(n) << endl;
}